import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class NonDecreasingSubsequences {
    /*
    * 491. 递增子序列
    * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，
    * 递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
    * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
    *
    * 1 <= nums.length <= 15
    * -100 <= nums[i] <= 100
    * */
    public static void main(String[] args){
        NonDecreasingSubsequences o = new NonDecreasingSubsequences();
        o.mySolution(new int[]{1,2,3,4,5,6,7,8,9,10,1,1,1,1,1});
        o.res.forEach(list -> {
            list.forEach(i->System.out.print(i+" "));
            System.out.println();
        });
    }

    // 我的想法：首先题目说返回递增子序列，那当然是先排序，排完序后，题目的要求转化为大小至少为2的非重复子集
    // 错了！！！本题不能排序！！！
    public List<List<Integer>> mySolution(int[] nums){
        backTracking(nums, 0);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backTracking(int[] nums, int start){
        if(path.size() >= 2)
            res.add(new ArrayList<>(path));
        if(start >= nums.length)
            return;
        int[] used = new int[201];  // 用来做hash，记录本层重复元素
        for (int i = start; i < nums.length; i++) {
            // 这个才是正儿八经的截断以及去重，在这里判断是否递增，以及元素在本层是否已经使用
            if((!path.isEmpty() && nums[i] < path.peekLast()) || used[nums[i]+100] == 1)
                continue;
            used[nums[i]+100] = 1;  // 标记该元素已经使用
            path.add(nums[i]);
            backTracking(nums, i+1);
            path.pollLast();
        }
    }
}
